/*
 * main.cpp
 *
 *  Created on: 14 déc. 2012
 *      Author: lbarouty
 */
#include <iostream>
#include <stdlib.h>
#include <omp.h>
#include "utils.h"

using namespace std ;

int taille;

inline void initTab(int* tab){

	for(int i=0; i<taille; ++i) tab[i] = rand();
}

void fusion(int tableau[], int deb1, int fin1, int fin2)
{
	int *table1;
	int deb2=fin1+1;
	int compt1=deb1;
	int compt2=deb2;
	int i;

	table1 = (int*)malloc((fin1-deb1+1)*sizeof(int));

	//on recopie les éléments du début du tableau
	for(i=deb1;i<=fin1;i++)
	{
		table1[i-deb1]=tableau[i];
	}

	for(i=deb1;i<=fin2;i++)
	{
		if (compt1==deb2) //c'est que tous les éléments du premier tableau ont été utilisés
		{
			break; //tous les éléments ont donc été classés
		}
		else if (compt2==(fin2+1)) //c'est que tous les éléments du second tableau ont été utilisés
		{
			tableau[i]=table1[compt1-deb1]; //on ajoute les éléments restants du premier tableau
			compt1++;
		}
		else if (table1[compt1-deb1]<tableau[compt2])
		{
			tableau[i]=table1[compt1-deb1]; //on ajoute un élément du premier tableau
			compt1++;
		}
		else
		{
			tableau[i]=tableau[compt2]; //on ajoute un élément du second tableau
			compt2++;
		}
	}
	free(table1);
}


void tri_fusion_bis(int tableau[],int deb,int fin)
{
	if (deb!=fin)
	{
		int milieu=(fin+deb)/2;
		tri_fusion_bis(tableau,deb,milieu);
		tri_fusion_bis(tableau,milieu+1,fin);
		fusion(tableau,deb,milieu,fin);
	}
}

void tri_fusion(int tableau[],int longueur)
{
	if (longueur>0)
	{
		tri_fusion_bis(tableau,0,longueur-1);
	}
}

void echanger(int *tab, int a, int b)
{
	int temp = tab[a];
	tab[a] = tab[b];
	tab[b] = temp;
}

void triPair(int *tab, const int k, int taille, int nbProcs) {
	int i = k ;
	int j = i + taille/nbProcs ;
	int size = taille/nbProcs ;
	tri_fusion_bis(tab, k, k+2*size-1);

	/*while(i < k+size && j < k+(2*size)) {
		if(tab[j] < tab[i]) {
			echanger(tab, j, i);
			i++ ;
		}
		else {
			i++ ;
			j++ ;
		}
	}*/
}

void triImpair(int *tab, const int k, int taille, int nbProcs) {
	int i = k ;
	int j = i + taille/nbProcs ;
	int size = taille/nbProcs ;
	tri_fusion_bis(tab, k, k+2*size-1);

	/*while(i < k+size && j < k+(2*size)) {
		if(tab[j] < tab[i]) {
			echanger(tab, j, i);
			i++ ;
		}
		else {
			i++ ;
			j++ ;
		}
	}*/
}

void afficher(int *tab, int taille) {
	for(int i = 0 ; i<taille ; i++) {
		cout << tab[i] << " ";
	}
	cout << endl ;
}

int main(int argc, char **argv) {
	int numProc ;
	int nbProcs = omp_get_num_procs();
//	const int taille = 16 ;
//	int tab[taille] = { 8, 3, 12, 10, 16, 5, 2, 18, 11, 13, 1, 20, 6, 4, 9, 17 } ;
	taille = 2000000;
	int tab[taille];
	initTab(tab);


//	afficher(tab,taille);

	for(int i=0 ; i<taille ; i += taille/nbProcs) {
//		cout << "Tri de " << i << " à " << i+(taille/nbProcs)-1 << endl ;
		tri_fusion_bis(tab, i, i+(taille/nbProcs)-1);
	}
//	afficher(tab,taille);

	/*cout << "TRI PAIR avec " << 0 << " " << taille << " " << nbProcs << endl ;
	triPair(tab, 0, taille, nbProcs);
	afficher(tab,taille);
	cout << "TRI PAIR avec " << 8 << " " << taille << " " << nbProcs << endl ;
	triPair(tab, 8, taille, nbProcs);
	afficher(tab,taille);
	cout << "TRI IMPAIR avec " << 4 << " " << taille << " " << nbProcs << endl ;
	triImpair(tab, 4, taille, nbProcs);
	afficher(tab,taille);

	cout << "TRI PAIR avec " << 0 << " " << taille << " " << nbProcs << endl ;
	triPair(tab, 0, taille, nbProcs);
	afficher(tab,taille);
	cout << "TRI PAIR avec " << 8 << " " << taille << " " << nbProcs << endl ;
	triPair(tab, 8, taille, nbProcs);
	afficher(tab,taille);
	cout << "TRI IMPAIR avec " << 4 << " " << taille << " " << nbProcs << endl ;
	triImpair(tab, 4, taille, nbProcs);
	afficher(tab,taille);*/
	Chrono c;
	c.Start();
	bool impair = false ;
//	afficher(tab,taille);
	if(taille % nbProcs == 0) {
		for(int zp=0 ; zp<nbProcs ; zp++) {
			// PARCOURS DES PROCESSEURS$
#pragma omp parallel for
			for(int i=0 ; i<nbProcs ; i+=2) {
				if(impair) i++;
				if(zp%2==0) {
					if(i+1<nbProcs) {
//						cout << "TRI PAIR avec " << i*nbProcs << " " << taille << " " << nbProcs << endl ;
						triPair(tab, i*nbProcs, taille, nbProcs) ;
					}
				}
				else {
					if(i+1<nbProcs) {
//						cout << "TRI IMPAIR avec " << i*nbProcs << " " << taille << " " << nbProcs << endl ;
						triImpair(tab, i*nbProcs, taille, nbProcs) ;
					}
				}
			}
			impair = !impair ;
		}
	}
	else {
		cout << "ERROR : " << nbProcs << " / " << taille << endl ;
	}
//	afficher(tab,taille);

	cout << endl ;
	cout << "Fin" << endl ;
	c.Stop();
}
